Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-10^4 <= Node.val <= 10^4
My Solution
We can solve this problem by recursively checking that the left subtree and right subtree are balanced. Then we can compute the depth of the left subtree and the right subtree and if they differ by more than 1 we return false. Otherwise we return true. Our base case is that if the node is null, we return 0 for the depth and true for the isBalanced function.
Time complexity would be O(n²) because computing the depth of every node is O(n). There are n nodes, so time complexity would O(n²). Space complexity would be O(1) since we only require constant extra space.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
if (!isBalanced(root.left) || !isBalanced(root.right)) {
return false;
}
int left = depth(root.left);
int right = depth(root.right);
return (Math.abs(left - right) <= 1);
}
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(1+depth(root.left), 1+depth(root.right));
}
}
We can improve on this by making a tradeoff between space and time. We can cache the depths as we compute them to reduce the time complexity to O(n). Space complexity would then be O(n) because the cache has n entries for the n depths.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
Map<TreeNode,Integer> cache = new HashMap<>();
return helper(root, cache);
}
public boolean helper(TreeNode root, Map<TreeNode,Integer> cache) {
if (root == null) {
return true;
}
if (!helper(root.left, cache) || !helper(root.right, cache)) {
return false;
}
int left = depth(root.left, cache);
int right = depth(root.right, cache);
return (Math.abs(left - right) <= 1);
}
public int depth(TreeNode root, Map<TreeNode,Integer> cache) {
if (root == null) {
return 0;
}
if (cache.containsKey(root)) {
return cache.get(root);
}
int left = 1 + depth(root.left, cache);
int right = 1 + depth(root.right, cache);
int d = Math.max(left, right);
cache.put(root, d);
return d;
}
}